package algorithm;
import java.util.*;

/*
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

 

示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。



class Solution {
    public int orangesRotting(int[][] grid) {

    }
}


 */
public class Main {
    public static void main(String[] args) {
        int[] nums1 = {2,3,1,2,4,3};
        int[] nums2 = {1,4,4};
        int[] nums3 = {1,1,1,1,1,1,1,1};

        System.out.println(getMinSubArr(nums1,7));
        System.out.println(getMinSubArr(nums2,4));
        System.out.println(getMinSubArr(nums3,11));

    }


    public static int getMinSubArr(int[] arr,int target){
        int count = Integer.MAX_VALUE;
        for (int i=0;i<arr.length;i++) {
            int sum=0;
            for(int j=i;j<arr.length;j++){
                sum+=arr[j];
                if (j-i+1>count){
                    break;
                }
                if (sum>=target){
                    if (j-i+1<count){
                        count = j-i+1;
                        break;
                    }
                }
            }
        }
        if (Integer.MAX_VALUE == count){
            return 0;
        }
        return count;
    }

    /**
     * 值 0 代表空单元格；
     * 值 1 代表新鲜橘子；
     * 值 2 代表腐烂的橘子。
     * @param grid
     * @return 最小分钟数
     */
    public static int orangesRotting(int[][] grid) {
        int result = 0;

        int m = grid.length;
        int n = grid[0].length;
        Stack<int[]> stack = new Stack();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2){
                    int[] index = new int[2];
                    index[0] = i;
                    index[1] = j;
                    stack.add(index);
                }
            }
        }


        while (!stack.empty()){
            result++;
            int[] curr = stack.pop();
            makeBad(stack,grid,curr[0],curr[1]);
        }

        return result;
    }

    private static int makeBad(Stack stack,int[][] grid, int i, int j) {
        int bad = 0;
        if (j+1<grid[0].length && grid[i][j+1] == 1){
            grid[i][j+1] = 2;

            int[] index = new int[2];
            index[0] = i;
            index[1] = j;
            stack.add(index);

        }
        if (j-1>=0 && grid[i][j-1] == 1){
            grid[i][j-1] = 2;

            int[] index = new int[2];
            index[0] = i;
            index[1] = j;
            stack.add(index);
        }

        if (i+1>=0 && grid[i+1][j] == 1){
            grid[i+1][j] = 2;

            int[] index = new int[2];
            index[0] = i;
            index[1] = j;
            stack.add(index);
        }
        if (i-1>=0 && grid[i-1][j] == 1){
            grid[i-1][j] = 2;

            int[] index = new int[2];
            index[0] = i;
            index[1] = j;
            stack.add(index);
        }

        return bad;
    }
}